% COMENTARIOS AGREGADOS Y TODOS:				%
%	- Estadística utilizada para la extracción de términos	%
%	- Método para realizar el Merge entre archivos		%

% Definición de los paquetes a utilizar. %

\documentclass{article}
\usepackage{latexsym}
\usepackage[utf8]{inputenx}
\usepackage[spanish]{babel}
\usepackage{graphicx}
\usepackage{anysize}
\usepackage{amsmath}
\usepackage{float}
\setlength{\skip\footins}{5cm}
\usepackage{lscape}
\usepackage{verbatim}
\usepackage{moreverb}
\usepackage{url}
\let\verbatiminput=\verbatimtabinput
\usepackage[nottoc,numbib]{tocbibind}
\setcounter{tocdepth}{4}
\setcounter{secnumdepth}{4}

%%%%%%%%%%%%%%%%%%%%%%%    MARGENES     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\marginsize{2cm}{2cm}{.5cm}{3cm} 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%     PORTADA     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% En la instrucción \title{..}, se escribe el título del documento.
\title{Trabajo Práctico: Indexación semántica latente}

% Aqui se pueden escribir los nombres de varios autores, separados por la instrucción \and.
\author{Lucas Simonelli \and Tomás Boccardo \and Gonzalo Beviglia} 

% Aquí podemos escribir la fecha de realización del trabajo práctico. La fecha actual se escribe con \today. Si no se quiere incluir la fecha, dejar la instrucción en blanco.
\date{ \today }

\begin{document}
		
\input{caratula.tex}

	\maketitle
	
	\tableofcontents
		
\newpage
		
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%      INTRODUCCIÓN     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	

\section{Introduccion}

\subsection{Objetivo}
El objetivo de este trabajo es construir un sistema que permita realizar búsquedas ranqueadas sobre una colección de documentos.
Para ello, se utilizará la indexación semántica latente (ver sección \ref{LSI}). 
	
La colección de documentos sobre la cual se buscará será un conjunto de archivos en formato texto e idioma inglés (el idioma
en realidad no es relevante).	
	
\subsection{Sobre LSI}\label{LSI}
La indexación semántica latente (de aquí en adelante, LSI, por sus siglas en inglés) es un método de indexación y recuperación
de datos que utiliza un método matemático llamado descomposición en valores singulares (DVS) para identificar patrones en las
relaciones entre los términos y conceptos contenidos en una colección de texto no estructurada. Para ver un ejemplo, puede consultarse la bibliografía.\cite{tutorial}
		
LSI se basa en el principio de que las palabras que se utilizan en los mismos contextos tienden a tener un significado similar.
Una característica clave de LSI es su capacidad para extraer el contenido conceptual de un cuerpo de texto mediante el
establecimiento de asociaciones entre los términos que aparecen en contextos similares.\cite{wikipedia}
			
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%      DESARROLLO     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage									
\section{Desarrollo}
	
\subsection{Parseado de los documentos}
% Indicar como se decide que es un término y que no. %
Los documentos a analizar se encontrarán ubicados en una carpeta, parámetro del programa. Deberán estar en formato texto y con extensión ".txt". Se abrirá cada documento en la carpeta y se lo recorrerá línea a línea, con el propósito de extraer los candidatos a convertirse en términos. 

\subsubsection{Extracción de los candidatos a términos}

En una primera fase, se extraeran conjuntos de palabras de hasta 3 componentes. Esto se basa en que, en idioma Inglés, un término difícilmente tenga más de éstas palabras. Sin embargo, la implementación de esta extracción se realizará de forma que la cantidad máxima de palabras que componen un término pueda variarse, para poder probar distintas posibilidades; se intentará lograr el mejor factor tiempo/calidad empíricamente.

Una vez que se extrajeron los precandidatos, se refinará ese conjunto mediante el uso de un método estadístico, más específicamente, de la información mútua -Mutual Information- (ver sección \ref{mi}). 


Se generarán subarchivos ordenados por cada documento, con la información extraída de los términos y sus pesos, calculados según se especifica en la sección \ref{peso}.

A continuación se construirá un árbol de términos con su correspondiente frecuencia de aparición
en el documento analizado. La estructura utilizada para almacenar los términos es la de Árbol AVL (Adelson-Velskii y Landis), elegida
por ser un árbol balanceado, en el que las consultas cuestan O(log n), con n la cantidad de pares (clave,valor) pertenecientes al árbol (para más información sobre esta estructura puede consultarse el inciso \ref{avl}).

La clave utilizada es el término en formato cadena, mientras que el valor utilizada es la frecuencia de aparición del candidato a término en el documento que está siendo analizado.

Luego de recorrer el documento, se contará con un árbol AVL con todos los candidatos a términos del documento. A partir
de aquí se eliminarán los no relevantes, en base a la información mútua (sección \ref{mi}). A medida que se recorre el árbol se escribe la información de cada par (clave,valor) del árbol en un archivo de texto,con el siguiente formato, para cada término:

%\vspace{5 mm}
% Formato con el que escribimos el archivo de texto.
\begin{verbatim}
término,id doc i,apariciones en doc i, ... ,id doc n,apariciones en doc n
cantidad de documentos en los que aparece el término
\end{verbatim}
%\vspace{5 mm}

El archivo se escribe con el formato descripto hasta que alcanza un determinado tamaño, luego de lo cual se lo cierra y se
continúa escribiendo otro sub-archivo. Estos subarchivos con las apariciones de los términos en cada documento se guardan
en una carpeta específica para este uso, definida dentro del programa.

Luego de que se analizaron todos los documentos, se procede a hacer un merge del conjunto de subarchivos creados.
El merge se realizará en dos fases, usando colas como buffers y un heap para ir extrayéndo la menor clave. Se utiliza
un buffer de entrada de tamaño fijo para cada uno de los archivos a mergear y un buffer de salida, también tamaño fijo
para minimizar las instancias en las que se escribe en disco. El tamaño del buffer de salida es mayor que los buffers
de entrada debido a que se busca acumular una gran cantidad de entradas antes de escribir al archivo destino.

\subsubsection{Estadística utilizada para la extracción de términos}\label{mi}

El refinamiento de los candidatos a términos es muy necesario, ya que la extracción de n-gramas como posibles términos genera varios términos por cada palabra. 
	
Por ejemplo, si se tiene ``hola que tal'', y se toman términos de hasta 3, esto resultaría en \{``hola'',``que'',``hola que'',``que tal'',``tal'',``hola que tal''\} (son 3! = 6 terminos).

Esto implica que la cantidad total de términos aumentará varias veces respecto de la original. Sin embargo, dentro de esos términos, hay muchos que no tienen sentido semántico (en el ej. anterior se puede observar). 

Por lo tanto, es necesario eliminar esos términos y mejorar la calidad de la información recolectada.

\paragraph{¿Por qué un filtro estadístico?}$\\$ 

A la hora de filtrar, hay dos formas generales de hacerlo: estadísticamente o lingüísticamente. Ante estas opciones, se eligió la primera. El motivo principal es la independencia idiomática que caracteriza a la LSI. Si se usaran filtros o recursos lingüísticos (stemming, identificación de frases, stopwords, etc), el sistema quedaría fuertemente ligado al idioma para el que se construyeron.

Entonces, al utilizar una estadística, si bien los textos a procesar estarán en inglés, el sistema podrá utilizarse para otros idiomas (mientras en ellos las palabras se separen por espacios, p.ej., para el chino no se podría) sin deber modificarlo, salvo tal vez en el mínimo MI permitido (ver sección \ref{minmi}).

\paragraph{Mutual Informatión (MI)}$\\$ 

% Lo explica el paper. seteando las variables minCount = 3, minLog = 5, minMutInfo = 2.5 %
La ecuaciones utilizadas para la extracción de términos en el proceso de parseo corresponden a el método de Información Mútua
(Mutual Information en ingles, MI).\cite{mi}

El método, se basa basicamente en relacionar la probabilidad de aparición conjunta del n-grama con las probabilidades de aparición marginales de las palabras que lo conforman. Los descripto anteriormente se expresa en la siguiente fórmula:

\[ mi(x,y) = \frac{ P(x_1,x_2, \cdots ,x_n) }{ P(x_1).P(x_2). \cdots .P(x_n) } \]

Donde:

$ P(x_1,x_2,...,x_n) $ es la probabilidad de aparición del término  \textbf{$(x_1,x_2,...,x_n)$} en el texto.

$ P(x_i)   $ es la probabilidad de aparición de la palabra \textbf{ $ x_i $ } en el texto.

Tomando la probabilidad como frecuencia sobre largo del documento, queda la expresión:

\[ mi(x,y) = \frac{ N^{n-1}.f(x_1,x_2, \cdots ,x_n) }{ f(x_1).f(x_2). \cdots .f(x_n) } \]

Donde:

$ f(x_1,x_2,...,x_n) $ es la frecuencia de aparición del término  \textbf{$(x_1,x_2,...,x_n)$} en el texto.

$ P(x_i)   $ es la frecuencia de aparición de la palabra \textbf{ $ x_i $ } en el texto.

$ N      $ es la cantidad total de candidatos a términos en el texto.

$ n      $ es la cantidad de componentes del término.

\paragraph{Filtrado}$\\$ 

Una vez que se calculó la MI para todos los n-gramas, se deben filtrar, eliminando del conjunto de candidatos los que tengan
$MI < MI_{MIN}$, éste último un parámetro variable, que debe ser estimado empíricamente. Ademas de filtrar por este parámetro
de mínimo valor del $MI$, no se consideraran como términos los n-gramas (con $n>1$) cuya frecuencia de aparición en el documento
sea igual a 1. Se tomó esta decisión debido a que, en algunos casos, dichos n-gramas cumplen con la condición del $MI_{MIN}$
debido a que la probabilidad de aparición del n-grama es igual a la probabilidad de aparición del término simple. En estos
casos optamos por no considerar a los n-gramas como términos porque no proveen una descripción cualitativa
del documento en el que aparecen.

\newpage
\paragraph{Experimentos realizados}\label{minmi}
\subparagraph{Primera prueba: 58 documentos (1.6 MB), 15979 palabras}
\begin{verbatimtab}[4]
MIN MI	CANT. TERM
0		190869
5		178111
12		104039
16		63936
20		30932
25		17892
30		16064
40		15979
50		15979
\end{verbatimtab}

\begin{figure}[H]
					\centering
					\includegraphics[width=13cm]{Imagenes/MI_58.png}
					\caption{Términos en función de mínima MI (58 docs)}
					\label{MI_58}
\end{figure}
Al aumentar mucho el MIN-MI se llega a un valor constante, que es el total de palabras.
\newpage
\subparagraph{Segunda prueba: 220 documentos (10.3 MB), 41343 palabras}
\begin{verbatimtab}[4]
MIN MI	CANT. TERM
0		1137151
5		1079816
12		650723
16		372065
20		151198
21		118058
23		76211
25		55652
30		41775
40		41343
50		41343
\end{verbatimtab}

\begin{figure}[H]
					\centering
					\includegraphics[width=13cm]{Imagenes/MI_220.png}
					\caption{Términos en función de mínima MI (220 docs)}
					\label{MI_220}
\end{figure}

Aquí empezamos a ver una tendencia a linealidad entre MIN MI = 5 y 20 (aprox). Agregaremos más documentos
para verificar esto:

\subparagraph{Tercer prueba: 365 documentos (16.5 MB), 55909 palabras}

\begin{verbatimtab}[4]
MIN MI	CANT. TERM
0		1909286
7		1676277
15		773248
20		265502
23		125621
25		85030
40		55909
50		55909
\end{verbatimtab}

\begin{figure}[H]
					\centering
					\includegraphics[width=13cm]{Imagenes/MI_353.png}
					\caption{Términos en función de mínima MI (365 docs)}
					\label{MI_365}
\end{figure}				

Vemos que la linealidad entre 5 y 20 se mantiene, y luego hay un decrecimiento más lento. Esto quiere decir que la eliminación de candidatos se va reduciendo al aumentar el mínimo mi, lo que resulta consistente con que los candidatos que van quedando son cada vez más importantes.

\paragraph{Valor óptimo estimado}$\\$ 

Con la información recolectada, se decide tomar MIN-MI = 20. Al elegir este valor, se estarán filtrando aprox. el 85\% de los candidatos, lo que representa una gran reducción de información sin significado.

% Lo de la exlusión de las palabras que aparecen en muchos documentos me parece que se tiene que hacer	
% en el merge, porque es cuando tenes información simultánea de más de un documento. Pero una pregunta	
% de a cuantos documentos a la vez vamos a hacer el merge? Porque no lo probe para buffers de entrada	
% muy chicos en tamaño, espero que ande. 								%
\begin{comment}
\newpage
\subsection{Método para realizar el Merge entre archivos}\label{merge}

El método utilizado para realizar el merge entre los n sub-archivos creados luego de parsear cuenta con la utilización
de una serie de n+1 colas. Se utilizan n colas, una por cada sub-archivo a mergear y una cola más que se utilizará
a modo de buffer. La cola de cada subarchivo tiene un tamaño fijado por el programa.

El merge comienza llenando la cola correspondiente a cada subarchivo hasta que la misma alcanza el tamaño máximo establecido
o el sub-archivo ha terminado. Luego de tener una cola llena de términos de cada archivo, se procede a llenar un heap con
una cantidad fija de términos de cada documento. Se utilizó esta estructura por ser una estructura en la que se desencola
de manera ordenada (alfabéticamente por nombre del término, en nuestro caso). La estructura del término que se extrae del
heap cuenta con un identificador de la cola de la que provino el mismo. El heap funciona como estructura intermedia
para ordenar los primeros k elementos del conjunto de las colas.

Una vez que una de las colas se queda sin elementos, se procede a llenarla nuevamente con términos del archivo parseado.
Se continúa haciendo esto hasta que el archivo este en condición de "End of file" y ya no haya que juntar más términos
de ese archivo.

El buffer cuenta, también, con un tamaño máximo mayor al de las colas de sub-archivos. Una vez que este alcanza su tamaño
máximo, se vuelca su contenido en el archivo destino del merge, con el mismo formato descrito anteriormente. Cuando todos
los archivos hayan terminado, se contará con un archivo destino en el que se mergearon todos los sub-archivos.

% Como hago para decir que vimos en la teórica que dos fases funcionan bien para la cantidad de documentos	%
% con la que vamos a trabajar? Me parece medio chanta poner "como vimos en la teorica", es muy poco informe.	%

La cantidad de fases con la que se realice el merge será una función de la cantidad de archivos totales que hayan
sido parseados. De esta manera no se generarán archivos intermedios innecesarios que obstruyan la eficiencia del
algoritmo utilizado por el merge. Se optimizarán las fases del merge ponderando la velocidad del mismo.

\end{comment}

\newpage
\subsection{Funciones de peso elegidas}\label{peso}\label{analisis-peso}
% Análisis preliminar de los posibles puntos fuertes y débiles de la fórmula elegida. Referencias. %

El valor asociado a un término en cada documento se ve representado por el valor que este toma en
la matriz generada, previamente a reducir a la misma en dimensiones. Para determinar este valor,
se utiliza una combinación de las funciones que describiremos. El conjunto de las funciones peso
se divide entre las funciones peso local ($l_{ij}$) y las de peso global ($g_i$).\cite{peso}

\vspace{5 mm}

\noindent Las funciones de peso locales entre las que se eligió la logarítmica fueron las siguientes:

\noindent \textbf{ Binaria: } $l_{ij}=1$ si el término $i$ está en el documento $j$ o $0$ si no está.

\noindent \textbf{ Frecuencia de término: } $l_{ij} = tf_{ij}$ la frecuencia del término $i$ en el documento $j$.

\noindent \textbf{ Logarítmica: } $l_{ij} = log(tf_{ij} + 1)$

\noindent \textbf{ Augnorm: } $l_{ij} = \frac{ \left( \frac{ tf_{ij} }{ max_i ( tf_{ij} ) } \right) + 1 }{2} $

\vspace{5 mm}

\noindent Las funciones de peso globales entre las que se eligió la entropía fueron las siguientes:

\noindent \textbf{ Binaria: } $g_i = 1$

\noindent \textbf{ Normalizada: } $ g_i = a + \frac {b}{\Sigma_j tf_{ij}^2} $, con $a$ y $b$ constantes.

\noindent \textbf{ IDF } (Inversa de la frecuencia en el documento): $g_i = log \left( \frac{n}{df_i} \right) $ con $df_i$ la cantidad de documentos en los que aparece el término $i$.

\noindent \textbf{ Entropía: } $g_i = 1 + \Sigma_j \frac{ p_{ij} log( p_{ij} ) }{log (n)} , p_{ij} = \frac{ tf_{ij} }{ gf_i } $ con $n$, la cantidad total de documentos, $gf_i$ la cantidad total de apariciones del término $i$ en los documentos.

\vspace{5 mm}

Se eligió una combinación entre varias de las fórmulas antedichas por el valor que tienen en determinado tipo
de corrección\cite{analisis-peso}. Las correcciones buscadas se explican a continuacion.

El principio de funcionamiento de la función logarítmica se basa en el hecho de que si un documento tiene una alta
aparición de un término a consultar, usualmente, este documento es más relevante que otro documento que contiene
dos términos de consulta con menor frecuencia. De esta manera, en general, muchas apariciones de un término consulta
contribuyen más que pocas apariciones de muchos términos consultados.

Se utiliza el la función IDF para descartar los términos que aperecen en muchos documentos que, al estar en muchos,
no deberían afectar la relevancia de cada documento en particular para una determinada consulta. Esto se basa en que
se ha observado que lo "común" que es una palabra se basa en su uso. De esta manera, se puede ver como un término
que aparece en todos los documentos $df_i \rightarrow n \Rightarrow ln \left( \frac{N}{df_i} \right) = 0$.

De no usarse una función que normalice las frecuencias y los pesos, se estaría permitiendo que documentos más largos
(y por ende con mas probabilidad de aparición de un determinado término) tengan mayor relevancia a la hora de realizar
una consulta. Por este motivo es que se utilizan funciones normalizadoras, que (en nuestro caso) limitan el peso
máximo que un término puede tener $max(A_{ij}) = 1$. La normalización que utilizaremos será aquella en la que
$a=b=0.5$ que es la utilizada por el sistema SMART (procesador de texto sofisticado que ha sido desarrollado
desde 1970).

\vspace{5 mm}

\noindent De esta manera, cada valor $i,j$ de la matriz completa $A$ será:
\[ A_{i,j} = log(tf_{ij} + 1) \cdot log \left( \frac{n}{df_i} \right) \cdot \left( 0.5 +\frac{0.5}{\Sigma_j tf_{ij}^2} \right) \]

\newpage
\subsection{Matriz inicial}
% Debe ser escalable. %

La matriz inicial se irá construyendo fila a fila en la última fase del merge. Cada fila representará las repeticiones por
término, y cada columna el documento donde se producen. Al estar ámbos ordenados por orden alfabético, se puede generar
un índice totalmente separado del archivo en el que se encuentra la matriz para la posterior utilización de los datos.

Se generarán, además del archivo en el que se encuentre la matriz, otros dos archivos, el índice de términos y el índice de documentos.

\subsubsection{Formato} 

La matriz se persistirá tomando en cuenta la gran ventaja que tiene de ser rala (es decir, tener muchos ceros). Por esta razon
no se guardará la matriz en forma densa (con cada valor cero tomado), sino como una matriz en formato "sparse", en la que solo se indican los
valores distintos de cero que esta posee en cada fila o columna, siendo, los restantes, valores iguales a cero.
Se almacenará en un archivo de texto como:

\begin{verbatimtab}[4]
NroFilas NroColumnas ValoresTotalesDistintosDeCero

Para cada fila:
	cantidadDeValoresDistintosDeCero
	para cada valor distinto de cero en la fila:
		indiceEnLaFila Valor
\end{verbatimtab}

(Los índices se cuentan desde cero).

Por ejemplo, la matriz

	\begin{displaymath}	
			\left( 
				\begin{array}{ccccc}
 					1 & 0 & 0 & 0 & 2.1 \\
 					0 & 0 & 3.3 & 0 & 0 \\
 					1 & 4 & 0 & 1 & 0 \\				
				\end{array}
			\right)
	\end{displaymath}
	
Se almacenará como:

\begin {verbatim}
3 5 6
2
0 1
4 2.1
1
2 3.3
3
0 1
1 4
3 1
\end{verbatim}

\noindent Utilizando corpus de texto de distintos tamaños como archivos de prueba, se obtuvieron los siguientes
tamaños de la matriz (con todas sus dimensions, previa a la reducción):

\begin{center}
    \begin{tabular}{ | l | p{5cm} |}
    \hline
    Tamaño Corpus (MB) & Tamaño Matriz (MB) \\ \hline
    0.151 & 0.109 \\ \hline
    9.9 & 3.3 \\ \hline
    54.8 & 21.5 \\
    \hline
    \end{tabular}
\end{center}

\noindent Con estos datos se puede ver que el tamaño de la matriz almacenada es un tamaño escalable
y razonable ya que, en promedio, el tamaño de la matriz completa es de alrededor de un
48\% del tamaño del corpus analizado. Los tamaños de las matrices obtenidas corresponden a matrices
con valores precisos hasta el primer decimal. Con mayor precision (6 o 7 decimales por valor),
la matriz pasa a ocupar alrededor de 10 veces el tamaño del corpus. Sin embargo, esta matriz será eliminada
luego de reducir las dimensiones, con lo que no debería ser un problema.

\newpage

\subsection{DVS}\label{dvs}

El método que se utilizará para la descomposición en valores singulares es el provisto por la biblioteca
SVDLIBC \cite{dvs}. Recibe un archivo con el formato explicado en la sección anterior.

Se generarán 3 archivos, con el mismo formato. Cada uno será, respectivamente, [U,$\Sigma$,V] de la
descomposición.

\[ A = U \Sigma V^T \]


SVDLIBC provee además de una opción para reducir las dimensiones de la descomposición, optimizada para matrices ralas.
En este caso:

\[ A = U_k {\Sigma}_k {V_k}^T \]

\noindent Donde:

$ k = \{ k \in R / \Sigma_k \in R^{k \times k} \} $

La matriz reducida se almacenará en el mismo formato que la matriz inicial. 

\newpage

\subsection{Consultas}
% Agregar ejemplos de utilización por línea de comando? %

Para realizar las consultas sobre los documentos analizados, se trabajará con un vector de consultas
(query vector: $q$), obtenido a partir de la cadena de texto consultada y el índice de términos almacenado
en archivo. En primer lugar se necesitará un vector de consulta intermedio ($Q$) necesario para obtener el
vector consulta en el espacio de dimensiones de la matriz reducida. Para construir el vector intermedio,
se colocará uno 1 en la posición del vector $Q$ correspondiente a un término si el mismo está siendo
consultado y un 0 en caso contrario.

\noindent Por ejemplo, si contamos con la siguiente lista de términos:

\vspace{5 mm}

\centerline{ \textbf{a, arrived, damaged, delivery, fire, gold, in, of, shipment, silver, truck} }

\vspace{5 mm}

\noindent y la consulta realizada es: \textbf{gold silver truck} el vector consulta intermedio será:

\[ Q^T = \left[ \begin{array}{ccccccccccc} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \end{array} \right] \]

\noindent Como nuestra DVS está reducida, debemos encontrar las coordenadas de este vector consulta en las nuevas dimensiones,
de modo de obtener nuestro vector de consulta ($q$). Se demuestra fácilmente que:

\[ q = Q^T U_k {\Sigma}_k^{-1} \]

De la DVS reducida, además podemos obtener los vectores asociados a cada documento analizado. Cada fila de
$ V_k $ representará al vector del documento $ i $, con $ i $ siendo el número de la fila.De aquí, ordenamos
la relevancia de los archivos respecto de su similitud del coseno con el vector consulta. Los documentos de
mayor similitud serán los más relevantes, en donde la similitud se obtiene como:

\[ sim(q,d) = \frac{ q \cdot d }{ |q| \cdot |d| } \]

\subsubsection{Ejemplos de consultas interesantes}
% Resultados esperados en base al diseño presentado. %

Para mantener consistencia con el diseño planteado en el parser, se transformará la consulta en un conjunto de n-gramas. Además de dar buenos resultados por sinonimia de términos (característica
inherente al método de LSI mediante la reducción de dimensiones), nuestro diseño dará resultados buenos cuando bastantes
n-gramas del string de consulta aparezcan en algun texto del corpus. Esto es de gran uso si se está intentando
encontrar una determinada frase (alguna en particular) en alguno de los textos del corpus.

\vspace{5 mm}

Por ejemplo la siguiente consulta: ``me parece algo muy razonable'', esta consulta es una bastante general, en el
sentido que no se está hablando de un tema en particular que pueda ser identificado. Al dividir esta consulta
en, por ejemplo, n-gramas de tamaño 3, obtendremos una gran relevancia en el texto en el que se encuentre dicha frase
completa, por la gran cantidad de matches. Siguiendo con la misma idea, cuanto más grande sean los anagramas con los
que se parsea el corpus obtendremos mejores resultados para apariciones de frases completas que están siendo consultadas.

\vspace{5 mm}

Debido a que  se considerarán a los números parseados como términos, dichos números aportarán relevancia a
los documentos. Ademas, si el número que se consulta tiene una estructura \textit{separada},
como puede ser un número de teléfono, obtendremos las mismas mejoras antes explicadas en base a los n-gramas.
Por ejemplo el siguiente número: ``15-6612-9220'' será dividido en (15,6612),(6612,9220),(15,6612,9220) considerándolo
de esta manera como 3 términos separados en vez de 1 número en su totalidad.

\vspace{5 mm}

Otro ejemplo interesante es la comparación entre dos documentos que aborden el mismo tema pero, al ser
un documento más extenso que el otro, en uno se traten los términos consultados con más frecuencia
absoluta (con frecuencia absoluta nos referimos a la cantidad de veces que aparece el término en el
documento). Por el otro lado, en el documento de menor extensión, los términos consultados tendrán
una menor frecuencia absoluta pero una mayor frecuencia relativa (es decir, una mayor proporcion
frecuencia:longitud del texto). Por la manera en la que se eligieron las funciones de peso, esperamos
que el texto de menor tamaño salga mejor ranqueado que el de mayor tamaño. Este sería el caso entre,
por ejemplo, un libro completo de recetas y una receta de un gaspacho de tomates cuando lo que se
está consultando es el string ``tomate''.

\vspace{5 mm}

Siguiendo con las funciones de peso, esperamos que las palabras \textit{separadoras} de texto en cada idioma
no aporten relevancia cuando no se trate de muchos matches de distintos n-gramas. Por ejemplo la consulta
``de una manera que todo sea bueno'' no debería arrojar resultados debido a palabras como ``de'',``una'',``que'',etc
a menos de que sea por un match largo de n-gramas.

\newpage

\subsection{Características de diseño aportadas por el grupo}
% Explicar por qué usamos el AVL y más o menos como funciona. Ventajas y desventajas respecto de ABB o Hash. %
Además de los aportes realizados en la estrategia de parseo, el filtro de términos y la función de peso elegida, se decidió usar un árbol AVL para 
ir manteniendo los términos en memoria.

\subsubsection{Árbol Adelson-Velskii Landis (AVL)}\label{avl}

Se utilizó el árbol AVL debido a que, no solo es una estructura que puede ser recorrida y obtener así los elementos
ordenados mediante un criterio, sino que, las consultas en este tipo de árbol son siempre O(log n), con n la cantidad
de elementos guardados en el árbol. Esto se debe a que el árbol realiza determinadas rotaciones siempre que se borre
o se agregue un elemento al mismo. Las rotaciones mantiene pareja la altura de cada rama del árbol, dada por la siguiente formula:
	    \[ h = \log_2 n \]
Siendo n la cantidad de elementos que se agregaron en el arbol.

Se prefirió este tipo de estructura por sobre el Árbol de Búsqueda Binaria y por sobre el Hash debido a que estas
dos estructuras no eran óptimas dentro del diseño planteado. El ABB no garantiza un tiempo de consulta constante,
sino que depende de la altura de la rama que se esté consultando. El hash, por otro lado, nos pérmite un tiempo
de consulta muy veloz pero, debido a que necesitamos los elementos ordenadamente, tendríamos que haber iterado
dentro de todo el hash y pasarlo a una estructura que ordene el conjunto de los datos, haciéndo que la solución
sea menos eficiente que la de usar un AVL. Otra ventaja que tiene el AVL sobre el hash es que, al estar limitada la memoria, el AVL dá la ventaja de utilizar solo la memoria necesaria para almacenar los datos, mientras que el hash posee un determinado tamaño fijo, que puede ocupar más memoria que la realmente necesaria.



\newpage
\begin{thebibliography}{9}

\bibitem{tutorial}
	\emph{Latent Semantic Indexing (LSI) How-to Calculations,}
	\url{http://www.miislita.com/information-retrieval-tutorial/svd-lsi-tutorial-4-lsi-how-to-calculations.html}
	
\bibitem{wikipedia}
 	Wikipedia,
  	\emph{Latent Semantic Indexing},
	\url{http://en.wikipedia.org/wiki/Latent_semantic_indexing}.

\bibitem{mi}
	\emph{A Statistical Corpus-Based Term Extractor},
	Patrick Pantel and Dekang Lin - Department of Computing Science, University of Alberta.

\bibitem{peso}
	\emph{Weight functions impact on LSA performance},
	Preslav Nakov, Antonia Popova, Plamen Mateev, Faculty of Mathematics and Informatics,
	Sofia University “St. Kliment Ohridski”.

\bibitem{analisis-peso}
	\emph{Term Weighting Revisited},
	Amitabh Kumar Singhal, Cornell University
	\url{http://ecommons.cornell.edu/bitstream/1813/7281/1/97-1626.pdf}.
	
\bibitem{parametros}% Lo use para intentar explicar las bondades de ciertas funciones peso %
	\emph{Latent Semantic Analysis Parameters for Essay Evaluation using Small-Scale Corpora},
	Universidad Autónoma de Madrid, Spain.
	
\bibitem{dvs}
	\emph{SVDLIBC library},
	\url{http://tedlab.mit.edu/~dr/SVDLIBC/}.

\end{thebibliography}
	
\end {document}
